Leetcode 2101

the algorithm of this question is not hard, simple bfs or dfs is sufficent, but the appoarch to link bombs together based on their radius takes a edge to come up with.

class Solution {
    public int maximumDetonation(int[][] bombs) {
        // we can treat as a graph
        Map<Integer,List<Integer>> graph = new HashMap<>();
        int n = bombs.length;

        // building the graph
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                // we need to make sure we have different bomb 
                if(i != j){
                    int xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
                    int xj = bombs[j][0], yj = bombs[j][1];

                    // if xi can trigger xj we create that edge
                    if((long) ri * ri >= (long)(xi - xj) * (xi - xj) + (long)(yi - yj) * (yi - yj)){
                        graph.putIfAbsent(i,new ArrayList<>());
                        graph.get(i).add(j);
                    }
                }
            }
        }

        // now we can do dfs or bfs 
        int res = 0;
        for(int i = 0; i < n; i ++){
            int count = bfs(i, new HashSet<>(),graph);
            res = Math.max(res,count);
        }
        return res;
    }
    private int bfs(int start, Set<Integer> visited, Map<Integer,List<Integer>> graph){
        Queue<Integer> q = new LinkedList<>();
        visited.add(start);
        q.add(start);
        int res = 0;
        while(!q.isEmpty()){
            res ++;
            int curr = q.poll();
            if(graph.containsKey(curr)){
                for(int next : graph.get(curr)){
                    if(!visited.contains(next)){
                        // this is a new valid bomb
                        q.add(next);
                        visited.add(next);
                    }
                }
            }

            
        }
        return res;
    }
}